Applicants' invention relates to apparatus and methods for communicating information securely, which is to say with reduced susceptibility to eavesdropping.
The widespread need for secure communication in radio communication systems is apparent. As just two examples, information relating to financial transactions is routinely exchanged by radio, and law enforcement officers often must communicate voice and/or data by radio. In both examples, it is critical that the communication be conducted with almost perfect secrecy, despite potential eavesdroppers' having access to strong information signals. Users of cellular radiotelephones also desire privacy in their communications, which may travel on links between mobile phones and base stations or on direct links between mobile phones.
One way of providing security is to encrypt the communicated information according to some system that the users have agreed in advance to use. Several encryption methods have been described in the literature, such as the data encryption standard (DES) and public key cryptography (PKC). As explained in W. Diffie et al., "Privacy and Authentication: An Introduction to Cryptography", Proc. IEEE vol. 67, pp. 397-427 (Mar. 1979), a classical cryptographic system is in general a set of instructions, a piece of hardware, or a computer program that can convert plaintext (unencrypted information) to ciphertext, or vice versa, in a variety of ways, one of which is selected by a specific key that is known to the users but is kept secret from others. The DES is a classical cryptographic system.
Popular PKC systems make use of the fact that finding large prime numbers is computationally easy but factoring the products of two large prime numbers is computationally difficult. PKC systems have an advantage over other cryptographic systems like the DES in that a PKC system uses a key for decryption (two large prime numbers) that is different from the key for encryption (the product of the two prime numbers, and an associated number). Thus, a PKC user's encryption key can be published for use by others, and the difficulty of securely distributing keys is avoided. See, e.g., R. I. Rivest et al., "A Method of Obtaining Digital Signatures and Public-Key Cryptosystems", Commun. of the ACM vol. 21, pp. 120-126 (Feb. 1978); and W. Diffie, "The First Ten Years of Public-Key Cryptography", Proc. IEEE vol. 76, pp. 560-577 (May 1988).
For either a classical or PKC system, the security of a message is dependent to a great extent on the length of the key, as described in C. E. Shannon, "Communication Theory of Secrecy Systems", Bell Sys. Tech. J. vol. 28, pp. 656-715 (Oct. 1949).
Unfortunately, it is often the case that two users (two police officers, for instance) do not share a secret key a priori, making secure real-time communication via a classical crytographic system impossible. Even a PKC system requires a user to generate a pseudo-random quantity. Moreover, popular PKC systems are unprovably secure, and suffer from severe requirements in computational complexity and amount of information that must be exchanged. As new ways of attacking PKC systems are mounted, PKC systems will retreat to ever longer exchange vectors (in effect, larger prime numbers) and ever more complex computations. As a result, classical and PKC cryptographic systems are less than ideal for many communication situations.
Complicating the task of any radio communication system is the variability of the radio channel caused by atmospheric disturbances, relative motion of the system users, changing radio signal reflections from structures and vehicles, etc. Such channel variability contributes to errors in the information communicated, and much effort is expended to overcome these errors. For example, some cellular radiotelephone systems convert analog information to be transmitted into digital information, which is then transformed according to a block error correction code. Such cellular radio systems are the North American digital advanced mobile phone service (D-AMPS), some of the characteristics of which are specified by the IS-54B and IS-136 standards published by the Electronic Industries Association and Telecommunications Industry Association (EIA/TIA), and the European GSM system.
In such time-division multiple access (TDMA) systems, each radio channel, or radio carrier frequency, is divided into a series of time slots, each of which contains a burst of information from a data source, e.g., a digitally encoded portion of a voice conversation. Successive time slots assigned to the same user, which are usually not consecutive time slots on the radio carrier, constitute the user's digital traffic channel, which may be considered a logical channel assigned to the user. During each time slot, 324 bits may be transmitted, of which the major portion, 260 bits, is due to the speech output of a coder/decoder (codec), including bits due to error correction coding of the speech output. The remaining bits are used for guard times and overhead signalling for purposes such as synchronization.
Other current cellular mobile telephone systems use analog FM to transmit speech. The three principal standards are the AMPS system in the U.S. that uses wideband FM with a spacing between channels of 30 KHz, the TACS system in the United Kingdom that uses 25 KHz channel spacings, and the NMT system in Scandinavia that uses narrow-band FM with 12.5 KHz channel spacings. In an effort to alleviate the capacity restrictions of the current analog FM systems, the D-AMPS and GSM systems, as well as systems in Japan, use digital transmission as described above. Another approach to increasing system capacity by reducing bandwidth requirements is a narrow-band FM system according to the NAMPS specification, which specifies a channel spacing of 10 KHz that is achieved by splitting each 30-KHz channel of AMPS into three parts.
FIGS. 1A, 1B illustrate an exemplary multi-layered cellular system. An umbrella macrocell 10 represented by a hexagonal shape (see FIG. 1A) is part of an overlying cellular structure comprising many macrocells A.sub.1 -A.sub.7, B.sub.1 -B.sub.7 (see FIG. 1B). Each umbrella cell may contain an underlying microcell structure. The radio coverage of the umbrella cell and an underlying microcell may overlap or may be substantially non-overlapping. The umbrella cell 10 includes microcells 20 represented by the area enclosed within the dotted line and microcells 30 represented by the area enclosed within the dashed line corresponding to areas along city streets, and picocells 40, 50, and 60, which cover individual floors of a building.
Briefly, control channels are used for setting up calls, informing the base stations about location and parameters associated with mobile stations, and informing the mobile stations about location and parameters associated with the base stations. The base stations listen for call access requests by mobile stations and the mobile stations in turn listen for paging messages. Once a call access message has been received, it must be determined which cell should be responsible for the call. Generally, this is determined by the signal strength of the mobile station received at the nearby cells. Next, the assigned cell is ordered, by the mobile switching center (MSC) for example, to tune to an available voice channel which is allocated from the set of voice channels accessible to the assigned cell.
FIGS. 2A-2C show exemplary time slot formats on a digital control channel (DCC) according to the IS-136 standard. Two possible formats for information sent from a mobile station to a base station are shown in FIGS. 2A and 2B, and a format for information sent from a base station to a mobile station is shown in FIG. 2C. These formats are substantially the same as the formats used for digital traffic channels (DTCs) under the IS-54B standard, but new functionalities are accorded to the fields in each slot in accordance with U.S. patent application Ser. No. 08/331,703 filed Oct. 31, 1994, which is expressly incorporated here by reference. In FIGS. 2A-2C, the number of bits in each field is indicated above that field. The bits sent in the G, R, PREAM, SYNC, SYNC+, and AG fields are used in a conventional way to help ensure accurate reception of the CSFP and DATA fields, e.g., for synchronization, guard times, etc. For example, the SYNC field would be the same as that of a DTC according to IS-54B and would carry a predetermined bit pattern used by the base stations to find the start of the slot. Also, the SYNC+ field would include a fixed bit pattern to provide additional synchronization information for the base stations, which would set their receiver gains during the PREAM field so as to avoid signal distortion.
FIG. 3 is a block diagram of an exemplary cellular mobile radiotelephone communication system for use with the cellular structure shown in FIGS. 1A, 1B and the time slot formats shown in FIGS. 2A-2C. The communication system includes a base station 110 that is associated with a respective one of the macrocell, microcell, and picocell; a mobile station 120; and an MSC 140. Each base station has a control and processing unit 130, which communicates with the MSC 140, which in turn is connected to the public switched telephone network (not shown). Each base station also includes at least one voice channel transceiver 150 and a control channel transceiver 160, which are controlled by the control and processing unit 130. The mobile station 170 includes a similar voice and control channel transceiver 170 for exchanging information with the transceivers 150, 160, and a similar control and processing unit 180 for controlling the voice and control channel transceiver 170. The mobile station's transceiver 170 can also exchange information with the transceiver 170 in another mobile station.
Other approaches to communication use systems called code division multiplexing (CDM) and code division multiple access (CDMA). In a conventional CDMA system, a digital information sequence to be communicated is spread, or mapped, into a longer digital sequence by combining the information sequence with a spreading sequence. As a result, one or more bits of the information sequence are represented by a sequence of N "chip" values. In one form of this process, called "direct spreading", each spread symbol is essentially the product of an information symbol and the spreading sequence. In a second form of spreading called "indirect spreading", the different possible information symbols are replaced by different, not necessarily related, spreading sequences. It will be understood that the information symbols may be produced by preceding stages of channel coding and/or spreading.
An advantage of such spreading is that information from many sources can be transmitted at the same time in the same frequency band, provided the spreading sequences used to represent the different sources' information sequences do not interfere with one another too much. In effect, the different spreading sequences correspond to different communication "channels". In general, there are 2.sup.N possible binary spreading sequences of length N chips, which results in a very large number of possible CDMA channels. This property of a CDMA system is sometimes called "soft capacity" because the number of channels is not restricted to N, as it would be in a frequency-division multiple access (FDMA) or a time-division multiple access (TDMA) system of the same bandwidth and data rate. Various aspects of conventional CDMA communications are described in K. Gilhousen et al., "On the Capacity of a Cellular CDMA System," IEEE Trans. Veh. Technol. vol. 40, pp. 303-312 (May 1991); and the following U.S. patent documents that are expressly incorporated here by reference: U.S. Pat. No. 5,151,919 to Dent; and U.S. Pat. No. 5,353,352 to Dent et al.; and U.S. patent application Ser. No. 08/155,557 filed Nov. 22, 1993, now U.S. Pat. No. 5,506,861.